package DecChallenges;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//https://leetcode.com/problems/design-a-food-rating-system/?envType=daily-question&envId=2023-12-17
//手写大顶堆做
//不知道为什么最后一个过不了
public class Day10_P2353 {
    public static void main(String[] args) {
        String[] foods = {"kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"};
        String[] cuisines =  {"korean", "japanese", "japanese", "greek", "japanese", "korean"};
        int[] ratings = {9, 12, 8, 15, 14, 7};
        FoodRatings system = new FoodRatings(foods, cuisines, ratings);
        System.out.println(system.highestRated("japanese"));
        system.changeRating("sushi", 16);
        System.out.println(system.highestRated("japanese"));
        system.changeRating("ramen", 16);
        System.out.println(system.highestRated("japanese"));

//        recognizer(ans, mine);
    }

    public static void recognizer(String[] s1, String[] s2) {
        List<String> ans = new ArrayList<>();
        List<String> mine = new ArrayList<>();
        int len1 = s1.length;
        int len2 = s2.length;
        for(int i = 0; i < Math.min(len1, len2); i++) {
            if(s1[i] == null && s2[i] == null) continue;
            if(s1[i] == null && s2[i] != null) {
                ans.add("null");
                mine.add(s2[i]);
            } else if(s2[i] == null && s1[i] != null) {
                ans.add(s1[i]);
                mine.add("null");
            } else if(!s1[i].equals(s2[i])) {
                ans.add(s1[i]);
                mine.add(s2[i]);
            }
        }
        for(int i = 0; i < ans.size(); i++) {
            System.out.println("================");
            System.out.println(ans.get(i));
            System.out.println(mine.get(i));
        }
    }
}

class FoodRatings {
    /*
    * define a heap whose element can be modified
    * */
    public static class MyHeap{
        String myCuisine;
        String[] heap;
        int size;
        HashMap<String, Integer> indexMap;

        public MyHeap(int len, String cuisine) {
            heap = new String[len];
            indexMap = new HashMap<>();
        }

        public void modifyIndex(String food) {
            int curIndex = indexMap.get(food);
            heapInsert(curIndex);
            heapify(curIndex);
        }

        public void add(String food) {
            heap[size] = food;
            indexMap.put(food, size);
            heapInsert(size++);
        }

        //big heap
        //insert: compare with its parent, if it is bigger than parent, go up
        private void heapInsert(int index) {
            while(index > 0) {
                if(myComparator(heap[index >> 1], heap[index]) < 0) {
                    swap(index >> 1, index);
                    index >>= 1;
                }else break;
            }
        }

        //big heap
        //heapify: compare with its offspring, if it is smaller than offspring, go down
        private void heapify(int index) {
            int leftKidIndex = (index << 1) + 1;
            while(leftKidIndex < size) {
                int rightKidIndex = leftKidIndex + 1;
                int biggerIndex = rightKidIndex < size &&
                        myComparator(heap[leftKidIndex], heap[rightKidIndex]) < 0 ?
                        rightKidIndex : leftKidIndex;
                if(myComparator(heap[index], heap[biggerIndex]) < 0) {
                    swap(index, biggerIndex);
                    index = biggerIndex;
                    leftKidIndex = (index << 1) + 1;
                }else break;
            }
        }

        private void swap(int i1, int i2) {
            indexMap.put(heap[i1], i2);
            indexMap.put(heap[i2], i1);
            String temp = heap[i1];
            heap[i1] = heap[i2];
            heap[i2] = temp;
        }

        private boolean isEmpty() {
            return size == 0;
        }
        public String peek() {
            return heap[0];
        }
    }

    private static HashMap<String, MyHeap> cuisineHeapMap; //a map to store different cuisines
    private static HashMap<String, Integer> ratingMap;//a map to store diff food's rating
    private static HashMap<String, List<String>> diffFoodMap; //a map to record how many diff food each cuisine has
    private static HashMap<String, String> foodCuisineMap;
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        //init maps
        cuisineHeapMap = new HashMap<>();
        ratingMap = new HashMap<>();
        diffFoodMap = new HashMap<>();
        foodCuisineMap = new HashMap<>();

        for(int i = 0; i < foods.length; i++) {
            String curFood = foods[i];
            String curCuisine = cuisines[i];
            int curRate = ratings[i];
            ratingMap.put(curFood, curRate);
            foodCuisineMap.put(curFood, curCuisine);
            if(!diffFoodMap.containsKey(curCuisine)) {
                diffFoodMap.put(curCuisine, new ArrayList<>());
            }
            diffFoodMap.get(curCuisine).add(curFood);
        }

        initHeapMap();
    }

    private void initHeapMap() {
        for(String cuisine: diffFoodMap.keySet()) {
            List<String> foodList = diffFoodMap.get(cuisine);
            int diffFoods = foodList.size();
            cuisineHeapMap.put(cuisine, new MyHeap(diffFoods, cuisine));
            MyHeap myHeap = cuisineHeapMap.get(cuisine);
            for(String food: foodList) {
                //init heap
                myHeap.add(food);
            }
        }
    }
    public void changeRating(String food, int newRating) {
        ratingMap.put(food, newRating);
        String cuisine = foodCuisineMap.get(food);
        MyHeap myHeap = cuisineHeapMap.get(cuisine);
        myHeap.modifyIndex(food);
    }
    public String highestRated(String cuisine) {
        MyHeap myHeap = cuisineHeapMap.get(cuisine);
        return myHeap.peek();
    }
    private static int myComparator(String food1, String food2) {
        int r1 = ratingMap.get(food1);
        int r2 = ratingMap.get(food2);
        if(r1 != r2) {
            return r1 - r2;
        } else {
            for(int i = 0; i < Math.min(food1.length(), food2.length()); i++) {
                char c1 = food1.charAt(i);
                char c2 = food2.charAt(i);
                if(c1 != c2) {
                    return c1 > c2 ? -1 : 1;
                }
                
            }
        }
        //never reached
        return 114514;
    }
}
